package com.hc.programming.string;

/**
 * 给你一个字符串 s ，请你反转字符串中 单词 的顺序。
 * 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
 * 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
 * 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
 * <p>
 * 示例 1：
 * 输入：s = "the sky is blue"
 * 输出："blue is sky the"
 * 示例 2：
 * 输入：s = "  hello world  "
 * 输出："world hello"
 * 解释：反转后的字符串中不能存在前导空格和尾随空格。
 * 示例 3：
 * 输入：s = "a good   example"
 * 输出："example good a"
 * 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
 * <p>
 * 提示：
 * 1 <= s.length <= 104
 * s 包含英文大小写字母、数字和空格 ' '
 * s 中 至少存在一个 单词
 * <p>
 * 进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/28 12:30
 */
public class 反转字符串中的单词 {
    public static void main(String[] args) {
        System.out.println(reverseWords("the sky is blue") + "===blue is sky the");
        System.out.println(reverseWords("  hello world  ") + "===world hello");
        System.out.println(reverseWords("a good   example") + "===example good a");
        System.out.println(reverseWords("F R  I   E    N     D      S      ") + "===S D N E I R F");
    }

    public static String reverseWords(String s) {
//        return OnFor(s);
//        return OnWhile(s);

        return O1(s);
    }

    /**
     * O(1) 空间复杂度 + 双指针
     * @param s
     * @return
     */
    private static String O1(String s) {
        char[] chars = s.toCharArray();
        int slow = 0;
        int fast = 0;
        int wordLen = 0;
        while (fast < chars.length) {
            if (chars[fast] == ' ') {
                if (wordLen > 0) {
                    reverse(chars, slow, fast - 1);
                    slow += wordLen;
                    wordLen = 0;
                }
                if (slow > 0 && chars[slow - 1] != ' ') chars[slow++] = ' ';
            } else {
                wordLen++;
                if (fast == chars.length - 1) {
                    reverse(chars, slow, fast);
                    slow += wordLen;
                }
            }
            fast++;
        }
        if (slow == 0) return s;
        if (chars[slow - 1] == ' ') slow--;
        reverse(chars, 0, slow - 1);
        return new String(chars, 0, slow);
    }

    private static void reverse(char[] chars, int start, int end) {
        while (start < end) {
            char temp = chars[start];
            chars[start++] = chars[end];
            chars[end--] = temp;
        }
    }

    /**
     * O(n) 空间复杂度 + for 循环
     *
     * @param s
     * @return
     */
    private static String OnWhile(String s) {
        if (s == null || s.isEmpty()) return s;
        char[] chars = s.toCharArray();
        int l = chars.length - 1;
        int r = l;
        int index = 0;
        char[] result = new char[chars.length];
        while (l >= 0) {
            if (chars[l] == ' ') {
                if (index > 0 && result[index - 1] != ' ') result[index++] = ' ';
                r--;
            } else {
                while (l >= 0 && chars[l] != ' ') {
                    l--;
                }
                for (int i = l + 1; i <= r; i++) {
                    result[index++] = chars[i];
                }
                r = l - 1;
                if (l > 0 && index < chars.length) result[index++] = ' ';
            }
            l--;
        }
        if (index == 0) return s;
        if (result[index - 1] == ' ') return new String(result, 0, index - 1);
        return new String(result, 0, index);
    }

    /**
     * O(n) 空间复杂度 + for 循环
     *
     * @param s
     * @return
     */
    private static String OnFor(String s) {
        if (s == null || s.isEmpty()) return s;
        char[] chars = s.toCharArray();
        char[] result = new char[chars.length];
        int r = chars.length - 1;
        int index = 0;
        for (int l = chars.length - 1; l >= 0; l--) {
            if (index == 0 && chars[l] == ' ' && l == r) {
                r--;
            } else if (chars[l] == ' ') {
                if (l < r) {
                    for (int i = l + 1; i <= r; i++) {
                        result[index++] = chars[i];
                    }
                }
                r = l - 1;
                if (result[index - 1] != ' ') result[index++] = ' ';
            } else if (l == 0 && chars[l] != ' ') {
                for (int i = l; i <= r; i++) {
                    result[index++] = chars[i];
                }
            }
        }
        if (index == 0) return s;
        if (result[index - 1] == ' ') return new String(result, 0, index - 1);
        return new String(result, 0, index);
    }
}
